Bitap algorithmで使う最大Levenstein距離を検索文字列長から算出する計算式の検討
こんなのを考えている
table:list
文字列長 編集距離
1 0
2 0
3 1
4 1
5 2
6 2
7 2
8 2
9 3
10 3
11 3
12 3
13 3
14 3
15 4
16 4
17 4
18 4
19 4
20 4
21 4
22 4
23 4
24 4
ある最大編集距離を使う文字列長の範囲を、$ 2,2,4,6,10,16,26,\cdotsのようにFibonacci数列と同じ増加速度で増やしていく 実際には$ 26の途中までしか使わない
編集距離は6まで計算できれば十分
立式
文字列長が有限なので、各文字列長に対して編集距離を決め打ちで返しても問題ない
でもできることなら四則演算と丸め込みだけで求めたいところ
漸化式
$ x: 編集距離からそれを適用する文字列長の範囲の要素数を返す函数
$ x(0)=2
$ x(1)=2
$ x(n+2)=x(n)+x(n+1)
解
$ \alpha+\beta=1\land\alpha\beta=-1とすると、
$ x(n+2)-\alpha x(n+1)=\beta(x(n+1)-\alpha x(n))
$ x(n+2)-\beta x(n+1)=\alpha(x(n+1)-\beta x(n))
一般項は
$ x(n+2)-\alpha x(x+1)=\beta^{n+1}(x(1)-\alpha x(0))=2\beta^{n+1}(1-\alpha)=2\beta^{n+2}
$ x(n+2)-\beta x(x+1)=\alpha^{n+1}(x(1)-\beta x(0))=2\alpha^{n+1}(1-\beta)=2\alpha^{n+2}
$ \implies\begin{pmatrix}1&-\alpha\\1&-\beta\end{pmatrix}\begin{pmatrix}x(n+2)\\x(n+1)\end{pmatrix}=2\begin{pmatrix}\beta^{n+2}\\\alpha^{n+2}\end{pmatrix}
$ \iff\begin{pmatrix}x(n+2)\\x(n+1)\end{pmatrix}=2\frac1{\alpha-\beta}\begin{pmatrix}-\beta&\alpha\\-1&1\end{pmatrix}\begin{pmatrix}\beta^{n+2}\\\alpha^{n+2}\end{pmatrix}
$ \iff x(n)=2\frac{\alpha^{n+1}-\beta^{n+1}}{\alpha-\beta}
編集距離$ nからそれが適用される最大文字列長を求める函数$ l(n)を求める
$ l(n)=\sum_{i=0}^{i=n} x(k)
ここで、$ a(n+1)-a(n)=\alpha^{n}\iff a=\frac1{\alpha-1}\alpha^nより、
$ \frac{2}{\alpha-\beta}\Delta\left(\frac{\alpha^{n+1}}{\alpha-1}-\frac{\beta^{n+1}}{\beta-1}\right)=x(n)
$ \therefore l(n)=\frac{2}{\alpha-\beta}\left(\frac{\alpha^{n+2}}{\alpha-1}-\frac{\beta^{n+2}}{\beta-1}-\frac{\alpha}{\alpha-1}+\frac{\beta}{\beta-1}\right)
$ =\frac{2}{\alpha-\beta}\left(\frac{\alpha^{n+2}}{\alpha-1}-\frac{\beta^{n+2}}{\beta-1}\right)+\frac{2}{(\alpha-1)(\beta-1)}
$ \alpha-1=-\beta, $ (\alpha-1)(\beta-1)=\alpha\beta-(\alpha+\beta)+1=-1, $ \alpha^2(\beta-1)=-\alpha^3より
$ =\frac{-2}{\alpha-\beta}\left(-\alpha^{n+3}+\beta^{n+3}\right)-2
$ =\frac{2\left(\alpha^{n+3}-\beta^{n+3}\right)}{\alpha-\beta}-2
これの逆函数$ l^{-1}(L)が、検索文字列長から対応する編集距離を求める函数となる
......これを愚直に計算させるより、決め打ちで値の対応表用意したほうがずっと速いよな